Data services are typically provided and consumed by a group of computing devices working together. For example, a data center supporting an Internet video streaming service may employ a variety of computing devices to respond to various user requests for content. Such services may designate one of the devices to be a “master node.” A designated master node may be given additional responsibilities for managing the service, such as arbitrating conflicts and authorizing new devices. Unfortunately, there are situations where a master node can fail, and might not be able to report its failure to the other devices in the service. A failed master node can lead to undesired service disruption, and while failures can be mitigated to some extent, they cannot completely be avoided. Accordingly, there is a constant need for improved methods for managing master and other node failures in a distributed service system.